package mo.leetcode_hot;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class L438 {


    public List<Integer> findAnagrams(String s, String p) {
        if (s == null || p == null || s.length() < p.length()) {
            return Collections.emptyList();
        }
        StringBuilder builder = new StringBuilder();
        List<Integer> res = new ArrayList<>();
        int target = p.length();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (p.indexOf(c) == -1) {
                builder.setLength(0);
            } else {
                builder.append(c);
                if (builder.length() == target) {
                    if (isAnagram(builder, p)) {
                        res.add(i+1-target);
                    }
                    builder.deleteCharAt(0);
                }
            }
        }
        return res;
    }

    private boolean isAnagram(StringBuilder builder, String p) {
        int[] counts = new int[26];
        for (char c : p.toCharArray()) {
            counts[c-'a']++;
        }
        for (int i = 0; i < builder.length(); i++) {
            int idx = builder.charAt(i)-'a';
            counts[idx]--;
            if (counts[idx] < 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        L438 test = new L438();
        System.out.println(test.findAnagrams("cbaebabacd", "abc"));
    }

}
